
"""
app id， 流量，域名个数，权重
app1, 5000, 10, 1
app2, 6000, 30, 3
......
app2000, 1200, 20, 4
共有2000个application, 每个application流量从0-7000，有1-100个域名，权重1-5
要求将所有application分成n组（n < 2000），要求
1. 各组总流量中，max - min <= 1000，
2. 各组单个应用平均权重，max - min <= 1，
3. 总域名个数小于等于500
"""
import random
import copy
import os


def produce_data():
    try:
        os.remove('./data.txt')
    except FileNotFoundError:
        pass

    data = []
    data_file = open('./data.txt', 'a')
    for i in range(20):
        row = []
        row.append("app{}".format(i))
        row.append(random.randint(0, 7000))
        row.append(random.randint(1, 100))
        row.append(random.randint(1,5))
        data_file.write("{},{},{},{}\n".format(*row))
        data.append(copy.deepcopy(row))
    return data    

data = produce_data()


class Balancer:
    def __init__(self, data):
        self.buckets_count = 4  # 分组个数
        self.data = data
        self.result_count = 0

        self.traffic_avg = sum([item[1] for item in data]) / 4
        self.traffic_threshold = 0.001
        self.traffic_top = self.traffic_avg * (1 + self.traffic_threshold)
        print("流量平均值: {}".format(self.traffic_avg))
        print("流量最大值: {}".format(self.traffic_top))

        self.weight_threshold = 0.2
        self.weight_avg = sum([item[3] for item in data]) / len(data)
        self.weight_top = self.weight_avg * (1 + self.weight_threshold)
        print("权重平均值: {}".format(self.weight_avg))
        print("权重最大值: {}".format(self.weight_top))

        self.domain_top = 1000
        print("域名个数最大值: {}".format(self.domain_top))
    
    def valid(self, buckets):
        if any([len(b) == 0 for b in buckets]):
            return False
        for b in buckets:
            # traffic = [item[1] for item in b]
            # domains = [item[2] for item in b]
            weights = [item[3] for item in b]
            if sum(weights)/len(weights) > self.weight_top:
                return False
        return True
    
    def start(self):
        buckets = [list() for _ in range(self.buckets_count)]
        buckets_traffic_sum = [0] * self.buckets_count
        # buckets_weight_sum = [0] * self.buckets_count
        buckets_domain_sum = [0] * self.buckets_count 
        def _backtrace(index):
            if index == len(self.data):
                if self.valid(buckets):
                    self.result_count += 1
                    Balancer.explain(buckets)
                return
            
            for i in range(self.buckets_count):
                if buckets_traffic_sum[i] + data[index][1] > self.traffic_top:
                    continue
                # if buckets_weight_sum[i] + data[index][3] > self.weight_avg * (len(buckets[i]) + 1):
                #     continue
                if buckets_domain_sum[i] + data[index][2] > self.domain_top:
                    continue
                buckets[i].append(data[index])
                buckets_traffic_sum[i] += data[index][1]
                # buckets_weight_sum[i] += data[index][3]
                buckets_domain_sum[i] += data[index][2]
                _backtrace(index+1)
                buckets_traffic_sum[i] -= data[index][1]
                # buckets_weight_sum[i] -= data[index][3]
                buckets_domain_sum[i] -= data[index][2]
                buckets[i].pop()
                if len(buckets[i]) == 0:
                    break
        _backtrace(0)
    
    @staticmethod
    def explain(buckets):
        print("======start=======")
        for b in buckets:
            traffic = [item[1] for item in b]
            domains = [item[2] for item in b]
            weights = [item[3] for item in b]
            print(sum(traffic), sum(domains), sum(weights)/len(weights))
        print("======end=======")


b = Balancer(data)
b.start()
print(b.result_count)


"""
1. 生成20个application的数据（流量，域名个数，权重）
2. 设定分组个数4
3. application分成4组后，每组的平均流量traffic_avg。
4. 回溯搜索所有分组可能性
    - 剪枝1：实时过滤每组流量总和大于traffic_avg * 1%
    - 剪枝2：实时过滤每组总域名数大于domain_top
    - 结果验证：分好组后，计算每组中，每app平均权重小于weight_top(weight_avg * 20%)
"""